package xyz.scootaloo.oj.offer

import org.junit.Test
import xyz.scootaloo.console.app.support.Tester

/**
 * @author flutterdash@qq.com
 * @since 2021/4/13 11:50
 */
class P11 {

    /**
     * |     |     |
     * 3, 4, 5, 1, 2
     *
     */
    private fun minArray(numbers: IntArray): Int {
        return findMinCore(numbers, 0, numbers.size / 2, numbers.size - 1)
    }

    private fun findMinCore(numbers: IntArray, left: Int, mid: Int, right: Int): Int {
        if (right - left <= 5)
            return findMin(numbers, left, right)
        val r = numbers[right]
        val l = numbers[left]
        var m = numbers[mid]
        if (l == m && m == r)
            return findMin(numbers, left, right)
        return when {
            m < l -> {
                m = (left + mid).shr(1)
                findMinCore(numbers, left, m, mid)
            }
            else -> {
                m = (mid + right).shr(1)
                findMinCore(numbers, mid, m, right)
            }
        }
    }

    private fun findMin(numbers: IntArray, left: Int, right: Int): Int {
        var min = numbers[left]
        for (idx in left + 1 .. right)
            if (numbers[idx] < min)
                min = numbers[idx]
        return min
    }

    @Test
    fun test0() {
        Tester.createTest(this::minArray)
            .addCase(intArrayOf(3, 4, 5, 1, 2), 1)
            .addCase(intArrayOf(3, 4, 5, 6, 1, 2), 1)
            .addCase(intArrayOf(2, 2, 2, 2, 0, 1), 0)
            .addCase(intArrayOf(4, 5, 6, 7, 0, 1, 2), 0)
            .testAndShow()
    }

}
